﻿// 402 遍历一般二叉树.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


using  namespace std;
/*
http://oj.daimayuan.top/course/7/problem/431

给你一棵 n个节点的二叉树，节点的编号为 1到 n
，二叉树的根为 1号节点。请你求出这棵二叉树的先序、中序和后序遍历的结果。

输入格式第一行一个整数 n表示节点数。

接下来 n行，每行两个整数，第一个整数表示 i号节点的左儿子的编号，
第二个整数表示 i号节点的右儿子的编号，如果某个数字为 0表示没有对应的子节点。

输入保证是一棵二叉树。

输出格式
输出三行，每行 n个数代表一种遍历的结果。

第一行为先序遍历的结果，第二行为中序遍历的结果，第三行为后序遍历的结果。

样例输入
4
2 3
0 0
4 0
0 0
样例输出
1 2 3 4
2 1 4 3
2 4 3 1
数据规模
对于所有数据，保证 1≤n≤1024。
*/


const int N = 1050;
int n;

struct NODE {
	int l, r, fa, depth;
}node[N];

void preorder(int x) {
	if (x > n || 0==x)return;
	cout << x << " ";
	preorder(node[x].l);
	preorder(node[x].r);
}

void inorder(int x) {
	if (x > n || 0 == x) return;
	inorder(node[x].l);
	cout << x << " ";
	inorder(node[x].r);
}

void postorder(int x) {
	if (x > n || 0 == x) return;
	postorder(node[x].l);
	postorder(node[x].r);
	cout << x << " ";
}


int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a, b; cin >> a >> b;
		if(a)
			node[i].l = a; node[a].fa = i;
		if(b)
			node[i].r = b; node[b].fa = i;
	}

	preorder(1); cout << endl;
	inorder(1); cout << endl;
	postorder(1); cout << endl;


	return 0;
}

 